import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author luoqingbo
 * @create 2024/4/29 9:42
 */
public class Leetcode1329 {
    public static void main(String[] args) {
        //mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
        int[][] mat = new int[][]{{3, 3, 1, 1}, {2, 2, 1, 2}, {1, 1, 1, 2}};
        System.out.println(Arrays.deepToString(diagonalSort(mat)));
    }

    public static int[][] diagonalSort(int[][] mat) {
        //1.先排序右上角
        for (int i = 0; i < mat[0].length; i++) {
            int x = 0;
            int y = i;
            sort(x, y, mat);
        }
        //2.再排序左下角
        for (int i = 0; i < mat.length; i++) {
            int x = i;
            int y = 0;
            sort(x, y, mat);
        }
        return mat;
    }

    public static void sort(int x, int y, int[][] mat) {
        int temp_x = x;
        int temp_y = y;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while (temp_x < mat.length && temp_y < mat[0].length) {
            pq.add(mat[temp_x][temp_y]);
            temp_x++;
            temp_y++;
        }
        while (x < mat.length && y < mat[0].length) {
            mat[x][y] = pq.poll();
            x++;
            y++;
        }
    }
}
